// Author: combacsa@kaist.ac.kr
// http://www.jungol.co.kr/prog/Hanal/hanalView.php?qs_code=1092

//#define COMPILE
#ifdef COMPILE

#include <fstream>
#include <iostream>
using namespace std;

int x;
int y;
int answer;

void input() {
	ifstream in("input.txt");
	in >> x >> y;
	in.close();
}

int mul(int x, int y) {
	x = x % 20091024;
	switch (y) {
	case 1:
		return x;
	case 2:
		return (x + x) % 20091024;
	default:
		int mid = y / 2;
		int ans = mul(x, mid);
		ans = (ans + ans) % 20091024;
		if (y % 2 == 1) ans = (ans + x) % 20091024;
		return ans;
	}
}

int power(int x, int y) {
	x = x % 20091024;
	switch (y) {
	case 1:
		return x;
	case 2:
		return mul(x, x) % 20091024;
	default:
		int mid = y / 2;
		int ans = power(x, mid);
		ans = mul(ans, ans) % 20091024;
		if (y % 2 == 1) ans = mul(ans, x) % 20091024;
		//cout << x << " ^ " << y << " == " << ans << endl;
		return ans;
	}
}

void solve() {
	if (y == 0)
		answer = 1;
	else
		answer = power(x, y);
}

void output() {
	ofstream out("output.txt");
	out << answer;
	out.close();
}

int main() {
	input();
	solve();
	output();
	return 0;
}
#endif
